#ifndef QUEUE_H
#define QUEUE_H

#endif // QUEUE_H
// queue standard header
#pragma once
#ifndef _QUEUE_
#define _QUEUE_
#ifndef RC_INVOKED
#include <algorithm>
#include <deque>
#include <vector>

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,_STL_WARNING_LEVEL)
 #pragma warning(disable: _STL_DISABLED_WARNINGS)
 _STL_DISABLE_CLANG_WARNINGS
 #pragma push_macro("new")
 #undef new
_STD_BEGIN
        // CLASS TEMPLATE queue
template<class _Ty,
    class _Container = deque<_Ty> >
    class queue
    {	// FIFO queue implemented with a container
public:
    typedef _Container container_type;
    typedef typename _Container::value_type value_type;
    typedef typename _Container::size_type size_type;
    typedef typename _Container::reference reference;
    typedef typename _Container::const_reference const_reference;

    static_assert(is_same_v<_Ty, value_type>, "container adaptors require consistent types");

    queue() _NOEXCEPT_COND(is_nothrow_default_constructible_v<_Container>) // strengthened
        : c()
        {	// construct with empty container
        }

    explicit queue(const _Container& _Cont)
        : c(_Cont)
        {	// construct by copying specified container
        }

    template<class _Alloc,
        class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
        explicit queue(const _Alloc& _Al)
            _NOEXCEPT_COND(is_nothrow_constructible_v<_Container, const _Alloc&>) // strengthened
        : c(_Al)
        {	// construct with empty container, allocator
        }

    template<class _Alloc,
        class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
        queue(const _Container& _Cont, const _Alloc& _Al)
        : c(_Cont, _Al)
        {	// construct by copying specified container, allocator
        }

    template<class _Alloc,
        class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
        queue(const queue& _Right, const _Alloc& _Al)
        : c(_Right.c, _Al)
        {	// construct by copying _Right container, allocator
        }

    explicit queue(_Container&& _Cont)
            _NOEXCEPT_COND(is_nothrow_move_constructible_v<_Container>) // strengthened
        : c(_STD move(_Cont))
        {	// construct by moving specified container
        }

    template<class _Alloc,
        class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
        queue(_Container&& _Cont, const _Alloc& _Al)
            _NOEXCEPT_COND(is_nothrow_constructible_v<_Container, _Container, const _Alloc&>) // strengthened
        : c(_STD move(_Cont), _Al)
        {	// construct by moving specified container, allocator
        }

    template<class _Alloc,
        class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
        queue(queue&& _Right, const _Alloc& _Al)
            _NOEXCEPT_COND(is_nothrow_constructible_v<_Container, _Container, const _Alloc&>) // strengthened
        : c(_STD move(_Right.c), _Al)
        {	// construct by moving _Right container, allocator
        }

    void push(value_type&& _Val)
        {	// insert element at beginning
        c.push_back(_STD move(_Val));
        }

    template<class... _Valty>
        decltype(auto) emplace(_Valty&&... _Val)
        {	// insert element at beginning
#if _HAS_CXX17
        return (c.emplace_back(_STD forward<_Valty>(_Val)...));
#else /* _HAS_CXX17 */
        c.emplace_back(_STD forward<_Valty>(_Val)...);
#endif /* _HAS_CXX17 */
        }

    _NODISCARD bool empty() const
        {	// test if queue is empty
        return (c.empty());
        }

    _NODISCARD size_type size() const
        {	// return length of queue
        return (c.size());
        }

    _NODISCARD reference front()
        {	// return first element of mutable queue
        return (c.front());
        }

    _NODISCARD const_reference front() const
        {	// return first element of nonmutable queue
        return (c.front());
        }

    _NODISCARD reference back()
        {	// return last element of mutable queue
        return (c.back());
        }

    _NODISCARD const_reference back() const
        {	// return last element of nonmutable queue
        return (c.back());
        }

    void push(const value_type& _Val)
        {	// insert element at beginning
        c.push_back(_Val);
        }

    void pop()
        {	// erase element at end
        c.pop_front();
        }

    const _Container& _Get_container() const
        {	// get reference to container
        return (c);
        }

    void swap(queue& _Right)
        _NOEXCEPT_COND(_Is_nothrow_swappable<_Container>::value)
        {	// exchange contents with _Right
        _Swap_adl(c, _Right.c);
        }

protected:
    _Container c;	// the underlying container
    };

#if _HAS_CXX17
template<class _Container,
    enable_if_t<!_Is_allocator<_Container>::value, int> = 0>
    queue(_Container)
        -> queue<typename _Container::value_type, _Container>;

template<class _Container,
    class _Alloc,
    enable_if_t<conjunction_v<
        negation<_Is_allocator<_Container>>,
        _Is_allocator<_Alloc>,
        uses_allocator<_Container, _Alloc>
    >, int> = 0>
    queue(_Container, _Alloc)
        -> queue<typename _Container::value_type, _Container>;
#endif /* _HAS_CXX17 */

template<class _Ty,
    class _Container,
    class = enable_if_t<_Is_swappable<_Container>::value>> inline
    void swap(queue<_Ty, _Container>& _Left,
        queue<_Ty, _Container>& _Right)
            _NOEXCEPT_COND(_NOEXCEPT_OPER(_Left.swap(_Right)))
    {	// swap _Left and _Right queues
    _Left.swap(_Right);
    }

template<class _Ty,
    class _Container>
    _NODISCARD inline bool operator==(const queue<_Ty, _Container>& _Left,
        const queue<_Ty, _Container>& _Right)
    {	// test for queue equality
    return (_Left._Get_container() == _Right._Get_container());
    }

template<class _Ty,
    class _Container>
    _NODISCARD inline bool operator!=(const queue<_Ty, _Container>& _Left,
        const queue<_Ty, _Container>& _Right)
    {	// test for queue inequality
    return (!(_Left == _Right));
    }

template<class _Ty,
    class _Container>
    _NODISCARD inline bool operator<(const queue<_Ty, _Container>& _Left,
        const queue<_Ty, _Container>& _Right)
    {	// test if _Left < _Right for queues
    return (_Left._Get_container() < _Right._Get_container());
    }

template<class _Ty,
    class _Container>
    _NODISCARD inline bool operator>(const queue<_Ty, _Container>& _Left,
        const queue<_Ty, _Container>& _Right)
    {	// test if _Left > _Right for queues
    return (_Right < _Left);
    }

template<class _Ty,
    class _Container>
    _NODISCARD inline bool operator<=(const queue<_Ty, _Container>& _Left,
        const queue<_Ty, _Container>& _Right)
    {	// test if _Left <= _Right for queues
    return (!(_Right < _Left));
    }

template<class _Ty,
    class _Container>
    _NODISCARD inline bool operator>=(const queue<_Ty, _Container>& _Left,
        const queue<_Ty, _Container>& _Right)
    {	// test if _Left >= _Right for queues
    return (!(_Left < _Right));
    }

        // CLASS TEMPLATE priority_queue
template<class _Ty,
    class _Container = vector<_Ty>,
    class _Pr = less<typename _Container::value_type> >
    class priority_queue
    {	// priority queue implemented with a _Container
public:
    typedef _Container container_type;
    typedef _Pr value_compare;
    typedef typename _Container::value_type value_type;
    typedef typename _Container::size_type size_type;
    typedef typename _Container::reference reference;
    typedef typename _Container::const_reference const_reference;

    static_assert(is_same_v<_Ty, value_type>, "container adaptors require consistent types");

    priority_queue()
        _NOEXCEPT_COND(is_nothrow_default_constructible_v<_Container>
            && is_nothrow_default_constructible_v<value_compare>) // strengthened
        : c(), comp()
        {	// construct with empty container, default comparator
        }

    explicit priority_queue(const _Pr& _Pred)
        _NOEXCEPT_COND(is_nothrow_default_constructible_v<_Container>
            && is_nothrow_copy_constructible_v<value_compare>) // strengthened
        : c(), comp(_Pred)
        {	// construct with empty container, specified comparator
        }

    priority_queue(const _Pr& _Pred, const _Container& _Cont)
        : c(_Cont), comp(_Pred)
        {	// construct by copying specified container, comparator
        _STD make_heap(c.begin(), c.end(), comp);
        }

    template<class _InIt>
        priority_queue(_InIt _First, _InIt _Last)
        : c(_First, _Last), comp()
        {	// construct by copying [_First, _Last), default comparator
        _STD make_heap(c.begin(), c.end(), comp);
        }

    template<class _InIt>
        priority_queue(_InIt _First, _InIt _Last, const _Pr& _Pred)
        : c(_First, _Last), comp(_Pred)
        {	// construct by copying [_First, _Last), specified comparator
        _STD make_heap(c.begin(), c.end(), comp);
        }

    template<class _InIt>
        priority_queue(_InIt _First, _InIt _Last, const _Pr& _Pred, const _Container& _Cont)
        : c(_Cont), comp(_Pred)
        {	// construct by copying [_First, _Last), container, and comparator
        c.insert(c.end(), _First, _Last);
        _STD make_heap(c.begin(), c.end(), comp);
        }

    template<class _Alloc,
        class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
        explicit priority_queue(const _Alloc& _Al)
            _NOEXCEPT_COND(is_nothrow_constructible_v<_Container, const _Alloc&>
                && is_nothrow_default_constructible_v<value_compare>) // strengthened
        : c(_Al), comp()
        {	// construct with empty container, allocator
        }

    template<class _Alloc,
        class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
        priority_queue(const _Pr& _Pred, const _Alloc& _Al)
            _NOEXCEPT_COND(is_nothrow_constructible_v<_Container, const _Alloc&>
                && is_nothrow_copy_constructible_v<value_compare>) // strengthened
        : c(_Al), comp(_Pred)
        {	// construct with empty container, comparator, allocator
        }

    template<class _Alloc,
        class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
        priority_queue(const _Pr& _Pred, const _Container& _Cont, const _Alloc& _Al)
        : c(_Cont, _Al), comp(_Pred)
        {	// construct by copying specified container, comparator, allocator
        _STD make_heap(c.begin(), c.end(), comp);
        }

    template<class _Alloc,
        class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
        priority_queue(const priority_queue& _Right, const _Alloc& _Al)
        : c(_Right.c, _Al), comp(_Right.comp)
        {	// construct by copying _Right, allocator
        }

    priority_queue(const _Pr& _Pred, _Container&& _Cont)
        : c(_STD move(_Cont)), comp(_Pred)
        {	// construct by moving specified container, comparator
        _STD make_heap(c.begin(), c.end(), comp);
        }

    template<class _InIt>
        priority_queue(_InIt _First, _InIt _Last, const _Pr& _Pred, _Container&& _Cont)
        : c(_STD move(_Cont)), comp(_Pred)
        {	// construct by copying [_First, _Last), moving container
        c.insert(c.end(), _First, _Last);
        _STD make_heap(c.begin(), c.end(), comp);
        }

    template<class _Alloc,
        class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
        priority_queue(const _Pr& _Pred, _Container&& _Cont, const _Alloc& _Al)
        : c(_STD move(_Cont), _Al), comp(_Pred)
        {	// construct by moving specified container, comparator, allocator
        _STD make_heap(c.begin(), c.end(), comp);
        }

    template<class _Alloc,
        class = enable_if_t<uses_allocator_v<_Container, _Alloc>>>
        priority_queue(priority_queue&& _Right, const _Alloc& _Al)
            _NOEXCEPT_COND(is_nothrow_constructible_v<_Container, _Container, const _Alloc&>
                && is_nothrow_move_constructible_v<value_compare>) // strengthened
        : c(_STD move(_Right.c), _Al), comp(_STD move(_Right.comp))
        {	// construct by moving _Right, allocator
        }

    void push(value_type&& _Val)
        {	// insert element at beginning
        c.push_back(_STD move(_Val));
        _STD push_heap(c.begin(), c.end(), comp);
        }

    template<class... _Valty>
        void emplace(_Valty&&... _Val)
        {	// insert element at beginning
        c.emplace_back(_STD forward<_Valty>(_Val)...);
        _STD push_heap(c.begin(), c.end(), comp);
        }

    _NODISCARD bool empty() const
        {	// test if queue is empty
        return (c.empty());
        }

    _NODISCARD size_type size() const
        {	// return length of queue
        return (c.size());
        }

    _NODISCARD const_reference top() const
        {	// return highest-priority element
        return (c.front());
        }

    void push(const value_type& _Val)
        {	// insert value in priority order
        c.push_back(_Val);
        _STD push_heap(c.begin(), c.end(), comp);
        }

    void pop()
        {	// erase highest-priority element
        _STD pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
        }

    void swap(priority_queue& _Right)
        _NOEXCEPT_COND(_Is_nothrow_swappable<_Container>::value
            && _Is_nothrow_swappable<_Pr>::value)
        {	// exchange contents with _Right
        _Swap_adl(c, _Right.c);
        _Swap_adl(comp, _Right.comp);
        }

protected:
    _Container c;	// the underlying container
    _Pr comp;	// the comparator functor
    };

#if _HAS_CXX17
template<class _Pr,
    class _Container,
    enable_if_t<conjunction_v<
        negation<_Is_allocator<_Pr>>,
        negation<_Is_allocator<_Container>>
    >, int> = 0>
    priority_queue(_Pr, _Container)
        -> priority_queue<typename _Container::value_type, _Container, _Pr>;

template<class _Iter,
    class _Pr = less<_Iter_value_t<_Iter>>,
    class _Container = vector<_Iter_value_t<_Iter>>,
    enable_if_t<conjunction_v<
        _Is_iterator<_Iter>,
        negation<_Is_allocator<_Pr>>,
        negation<_Is_allocator<_Container>>
    >, int> = 0>
    priority_queue(_Iter, _Iter, _Pr = _Pr(), _Container = _Container())
        -> priority_queue<_Iter_value_t<_Iter>, _Container, _Pr>;

template<class _Pr,
    class _Container,
    class _Alloc,
    enable_if_t<conjunction_v<
        negation<_Is_allocator<_Pr>>,
        negation<_Is_allocator<_Container>>,
        _Is_allocator<_Alloc>,
        uses_allocator<_Container, _Alloc>
    >, int> = 0>
    priority_queue(_Pr, _Container, _Alloc)
        -> priority_queue<typename _Container::value_type, _Container, _Pr>;
#endif /* _HAS_CXX17 */

template<class _Ty,
    class _Container,
    class _Pr,
    class = enable_if_t<_Is_swappable<_Container>::value && _Is_swappable<_Pr>::value>> inline
    void swap(priority_queue<_Ty, _Container, _Pr>& _Left,
        priority_queue<_Ty, _Container, _Pr>& _Right)
            _NOEXCEPT_COND(_NOEXCEPT_OPER(_Left.swap(_Right)))
    {	// swap _Left and _Right queues
    _Left.swap(_Right);
    }
_STD_END

namespace std {
template<class _Ty,
    class _Container,
    class _Alloc>
    struct uses_allocator<queue<_Ty, _Container>, _Alloc>
        : uses_allocator<_Container, _Alloc>::type
    {	// true_type if container allocator enabled
    };

template<class _Ty,
    class _Container,
    class _Pr,
    class _Alloc>
    struct uses_allocator<priority_queue<_Ty, _Container, _Pr>, _Alloc>
        : uses_allocator<_Container, _Alloc>::type
    {	// true_type if container allocator enabled
    };
}	// namespace std

 #pragma pop_macro("new")
 _STL_RESTORE_CLANG_WARNINGS
 #pragma warning(pop)
 #pragma pack(pop)
#endif /* RC_INVOKED */
#endif /* _QUEUE_ */

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */
